"""
单向链表
保护节点：头结点，尾节点，在插入删除时任意位置都是相同的操作，避免边界问题
空链表头结点指向none
头结点和尾节点不存储数据
单向链表一般只有头结点
"""
class Node():
    """
    创建结点
    """
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkList():
    def __init__(self):
        # 头结点
        self.head = Node()
        self.length = 0

    def append_node(self, data):
        """
        单向链表追加节点
        :param data:
        :return:
        """
        temp = self.head
        new_node = Node(data)
        # 只有一个头结点，在头结点后追加
        if temp.next is None:
            temp.next = new_node
        # 已经有存在的节点，从头结点开始遍历找到最后一个元素追加
        else:
            while temp.next is not None:
                temp = temp.next
            temp.next = new_node
        self.length = self.length + 1

    def insert_node(self, index, data):
        """
        单向链表插入节点，0-长度-1之间
        :param index: 插入的位置，从0开始
        :param data:
        :return:
        """
        if isinstance(index, int) is False or index < 0 or index > self.length-1:
            raise('索引不正确')
        temp = self.head
        new_node = Node(data)
        for i in range(self.length):
            if i == index:
                print(f'下标{index}插入新元素“{data}”')
                current = temp
                next_1 = temp.next
                current.next = new_node
                new_node.next = next_1
                self.length = self.length+1
                print('插入成功')
                print(self.length)
                break
            temp = temp.next

    def del_node(self, index):
        """
        单向链表删除节点
        :param index: 删除的数据的索引，从0开始
        :return:
        """
        if isinstance(index, int) is False or index < 0 or index > self.length-1:
            raise('索引不正确')
        temp = self.head
        for i in range(self.length):
            if i == index:
                print(f'下标{index}删除元素“{temp.next.data}”')
                next_1 = temp.next.next
                temp.next = next_1
                self.length = self.length-1
                print('删除成功')
            temp = temp.next

    def query_node(self, index):
        """
        根据索引查询
        :param index: 从0开始
        :return:
        """
        if isinstance(index, int) is False or index < 0 or index > self.length-1:
            raise('索引不正确')
        temp = self.head.next
        for i in range(self.length):
            if i == index:
                print(f'索引{index}数据为“{temp.data}”')
                break
            temp = temp.next

    def update_node(self, index, data):
        """
        根据索引修改数据
        :param index: 从0开始
        :return:
        """
        if isinstance(index, int) is False or index < 0 or index > self.length-1:
            raise('索引不正确')
        temp = self.head.next
        for i in range(self.length):
            if i == index:
                temp.data = data
                break
            temp = temp.next

    def print_list(self):
        """
        打印链表
        :return:
        """
        if self.head.next is None:
            print('空列表')
            return
        temp = self.head.next
        while temp:
            print(temp.data)
            temp = temp.next
        print('打印结束')

    def reverse_link_list(self):
        """
        反转链表：最后一个节点指向none，（1）获取到当前节点的下一个节点，保存
        （2）当前节点指向first
        （3）first指向当前节点
        （4）设置下一个节点尾当前节点
        （5）一直循环到当前节点的下一个节点是none，跳出循环
        :return:
        """
        # 1-2-3-4-5
        # 保存头结点
        temp = self.head
        # 第一个节点
        node_1 = temp.next
        first = None
        while True:
            # 当前结点的下一个节点
            node_2 = node_1.next
            node_1.next = first
            first = node_1
            # 要把头结点指向最后一个，在最后一个节点跳出循环，把node节点保存在当前节点，不指向none
            if node_2 is None:
                break
            node_1 = node_2
        temp.next = node_1

    def group_list(self, k):
        """
        k个一组进行反转
        1-2-3-4-5三个一组 3-2-1-4-5
        （1）按照k进行分组
        （2）调用上面的函数进行反转，如果剩余个数不足k个就不反转
        （3）把多个组之间进行连接--需要保存上一次的尾节点
        :param: k 反转一次的个数
        :return:
        """
        # 连接边的时候从last节点开始连接
        last = self.head
        # 第一个节点
        current = last.next
        i = 1
        start = None
        flag = True
        # 1找个一组的k个
        while flag:
            # 取到了k个，要把最后一个节点指向none
            if current is None:
                last.next = None
                break
            # 保存开始节点
            if i == 1:
                start = current
            # 取不到k个元素，直接连接第一个
            if current.next is None and i < k:
                last.next = start
                break
            # 正常可以取到k个
            elif i == k:
                end = current
                # 先保存当前的下一个节点
                end_next = end.next

                # 反转
                def reverse_list(first, second):  # first开始节点，second结束节点
                    node_1 = first.next  # 1-2-3-4-5-6
                    while node_1:
                        node_2 = node_1.next
                        node_1.next = first
                        if node_1 is second:
                            break
                        first = node_1
                        node_1 = node_2

                reverse_list(start, end)
                # 把两条边连接起来
                last.next = end
                last = start
                i = 1
                current = end_next
                continue
            current = current.next
            i = i + 1

a = LinkList()
a.append_node(1)
a.append_node(2)
a.append_node(3)
a.append_node(4)
a.append_node(5)
a.append_node(6)
# a.print_list()
# print('-------------插入------------------')
# a.insert_node(2, '哈哈哈')
# a.append_node('444444444')
# a.print_list()
# print('-------------删除------------------')
# a.del_node(0)
# a.print_list()
# a.query_node(2)
# # a.insert_node(5, '')
# a.update_node(1, 'dfjkgh')
# a.print_list()
# a.reverse_link_list()
# a.print_list()
a.group_list(5)
a.print_list()
